package com.lei.leetcode;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * @Author LeiXiaoLei
 * @Date 2022/8/12 14:59
 * @Version 1.0
 * <p>
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class S_215 {
    public int findKthLargest(int[] nums, int k) {
//        return selectK(nums, 0, nums.length - 1, nums.length - k, new Random());
        return findKthLargest(nums, 0, nums.length - 1, nums.length - k, new Random());
    }

    private int findKthLargest(int[] arr, int l, int r, int k, Random random) {
        while (r >= l) {
            int p = partition(arr, l, r, random);
            if (k == p) return arr[p];
            if (k < p) r = p - 1;
            else l = p + 1;
        }
        return -1;
    }

    private int selectK(int[] arr, int l, int r, int k, Random random) {
        int p = partition(arr, l, r, random);
        if (k == p) return arr[p];
        if (k < p) return selectK(arr, l, p - 1, k, random);
        return selectK(arr, p + 1, r, k, random);
    }

    private int partition(int[] arr, int l, int r, Random random) {
        int p = (l + random.nextInt(r - l + 1));
        swap(arr, l, p);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arr[i] < arr[l]) i++;
            while (j >= i && arr[j] > arr[l]) j--;
            if (i >= j) break;
            swap(arr, i++, j--);
        }
        swap(arr, l, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (!pq.isEmpty() && nums[i] > pq.peek()) {
                pq.remove();
                pq.add(nums[i]);
            }
        }
        return pq.peek();
    }

}
